package com.example.tencentTrain;

import java.util.Arrays;

/**
 * 给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
 *
 *  示例:
 *  输入: [1,2,3,4]
 * 输出: [24,12,8,6]
 */
public class Leetcode238_ProductExceptSelf {
    public static void main(String[] args) {

        int[] nums = {1, 2, 3, 4};
//        nums = new int[] {2, 3, 3, 4};

        int[] res = new Solution().productExceptSelf(nums);
        System.out.println(Arrays.toString(res));
    }

    static class Solution {
        private int[] productExceptSelf2(int[] nums) {
            if (nums == null) return null;
            int len = nums.length;
            int[] res = new int[len];
            // 先计算不包含自己的前缀乘积记录到res[i]中
            res[0] = 1;
            for (int i = 1; i < len; i++) {
                res[i] = res[i - 1] * nums[i - 1];
            }
            int sufProduct = 1; // 将后缀乘积的空间优化成常数级
            // 从后先前依次计算后缀乘积，并更新每个结果
            for (int i = res.length - 1; i >= 0; i--) {
                res[i] = res[i] * sufProduct;
                sufProduct *= nums[i];
            }
            return res;
        }

        private int[] productExceptSelf1(int[] nums) {
            if (nums == null) return null;
            int len = nums.length;
            int[] preProduct = new int[len]; // 不包含自己的前缀乘积
            int[] sufProduct = new int[len]; // 不包含自己的后缀的乘积
            int[] res = new int[len];
            // 逐个求前缀乘积
            preProduct[0] = 1;
            for (int i = 1; i < len; i++) {
                preProduct[i] = preProduct[i - 1] * nums[i - 1];
            }
            // 逐个求后缀乘积
            sufProduct[len - 1] = 1;
            for (int i = len - 2; i >= 0; i--) {
                sufProduct[i] = sufProduct[i + 1] * nums[i + 1];
            }

            for (int i = 0; i < len; i++) {
                res[i] = preProduct[i] * sufProduct[i];
            }
            return res;
        }

        public int[] productExceptSelf(int[] nums) {
            return productExceptSelf2(nums);
        }
    }
}
